from random import randint
from time import time

def down(a, x, la):
    if x<0 or x>=la:
        return
    i=x
    j,u = (i<<1)+1,a[i]
    while j<la :
        if j+1<la and a[j+1]>a[j] :
            j += 1
        if a[j]>u :
            a[i],i,j = a[j],j,(i<<1)+1
        else :
            break
    a[i] = u

def init(a) :
    la = len(a)
    h = la/2
    while h>=0 :
        down(a,h,la)
        h -= 1

def heap_sort(a) :
    init(a)
    la = len(a)-1
    while la>0 :
        a[0],a[la] = a[la],a[0]
        down(a,0,la)
        la -= 1

def main():
    n = int(input())
    nn = n*n;
    data = [randint(0,nn) for i in range(n)]
    # print data
    print 'heap sort begin:'
    print ' running...'
    t1 = int(time()*1000)
    heap_sort(data)
    t2 = int(time()*1000)
    print 'heap sort end.'
    # print data
    print 'run time: %dms'%(t2-t1)
    p = True
    for i in xrange(n-1) :
        if data[i]>data[i+1] :
            p = False
            break
    print 'the answer is '+('right'if p else'wrong')+' !!!'

if __name__ == '__main__' :
    main()
